#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

struct Interval {
    int start;
    int end
};

void swap(void* p1, void* p2, size_t data_size) {
    void* tmp = malloc(data_size);
    memcpy(tmp, p1, data_size);
    memcpy(p1, p2, data_size);
    memcpy(p2, tmp, data_size);
    free(tmp);
}

size_t partition(void* data, size_t total_size, size_t data_size, int (*compare)(const void*, const void*)) {
    if(total_size <= 1) {
        return 0;
    }

    //srand((unsigned)time(0));
    //size_t pivot_offset = rand()%total_size;
    size_t pivot_offset = 0;
    void* pivot = data+(pivot_offset)*data_size;
    swap(data, pivot, data_size);
    pivot = data;

    void* iter = data+data_size;
    size_t iter_offset = 1;
    size_t pos = 1; // left the pos will smaller(bigger) than pivot(exclude)

    while(iter_offset < total_size) {
        if(compare(pivot, iter)) {
            // pivot <= iter
            swap(iter, pivot+pos*data_size, data_size);
            pos++;
        } else {
        }
        iter += data_size;
        iter_offset++;
    }
    pos--;
    swap(pivot, pivot+pos*data_size, data_size);
    return pos;
}

void qsort(void* data, size_t total_size, size_t data_size, int (*compare)(const void*, const void*)) {
    if(total_size <= 1) {
        return ;
    }

    size_t pos = partition(data, total_size, data_size, compare);
    qsort(data, pos, data_size, compare);
    qsort(data+(pos+1)*data_size, total_size-pos-1, data_size, compare);
}

int compare_interval(const struct Interval* inter1, const struct Interval* inter2) {
    return inter1->start == inter2->start ? inter1->end >= inter2->end : inter1->start >= inter2->start;
}

struct Interval* merge(struct Interval* intervals, int intervalsSize, int* returnSize) {
    if(0 >= intervalsSize) {
        return NULL;
    }
    struct Interval* new_intervals = malloc(intervalsSize*sizeof(struct Interval));
    *returnSize = 0;
    qsort(intervals, intervalsSize, sizeof(struct Interval), compare_interval);
    size_t i = 0;
    struct Interval* first = NULL;
    struct Interval* second = intervals;
    for(; i<intervalsSize; i++) {
        first = new_intervals+*returnSize;
        if(*returnSize>0 && second->start <= (first-1)->end && second->end <= (first-1)->end) {
            // first contains second
        } else if(*returnSize>0 && second->start <= (first-1)->end && second->end > (first-1)->end) {
            // overlap
            (first-1)->end = second->end;
        } else {
            memcpy(first, second, sizeof(struct Interval));
            *returnSize = *returnSize+1;
        }
        second++;
    }
    return new_intervals;
}

int main(int argc, char** argv) {
    return 0;
}
